{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Integer Break"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: integerBreak"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #整数拆分"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个正整数&nbsp;<code>n</code>&nbsp;，将其拆分为 <code>k</code> 个 <strong>正整数</strong> 的和（&nbsp;<code>k &gt;= 2</code>&nbsp;），并使这些整数的乘积最大化。</p>\n",
    "\n",
    "<p>返回 <em>你可以获得的最大乘积</em>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>n = 2\n",
    "<strong>输出: </strong>1\n",
    "<strong>解释: </strong>2 = 1 + 1, 1 × 1 = 1。</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>n = 10\n",
    "<strong>输出: </strong>36\n",
    "<strong>解释: </strong>10 = 3 + 3 + 4, 3 ×&nbsp;3 ×&nbsp;4 = 36。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= n &lt;= 58</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [integer-break](https://leetcode.cn/problems/integer-break/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [integer-break](https://leetcode.cn/problems/integer-break/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['2', '10']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerBreak(self, n: int) -> int:\n",
    "        if(n<=3):\n",
    "            return n-1\n",
    "        n3=n//3\n",
    "        r3=n%3\n",
    "        if(r3==0):\n",
    "            return 3**n3\n",
    "        if(r3==1):\n",
    "            r3=4\n",
    "            n3-=1\n",
    "        return r3*(3**n3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerBreak(self, n: 'int') -> 'int':\n",
    "        if n <= 3:\n",
    "            if n == 3:\n",
    "                return 2\n",
    "            return 1\n",
    "        \n",
    "        value = 1\n",
    "        while n >= 3:\n",
    "            value*=3\n",
    "            n-=3\n",
    "        if n == 1:\n",
    "            value//=3\n",
    "            value*=4\n",
    "        elif n == 2:\n",
    "            value*=2\n",
    "        return value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    __ans = [0, 0, 1, 2, 4, 6, 9, 12, 18, 27, 36, 54, 81, 108, 162, 243, 324,\n",
    "    486, 729, 972, 1458, 2187, 2916, 4374, 6561, 8748, 13122, 19683, 26244,\n",
    "    39366, 59049, 78732, 118098, 177147, 236196, 354294, 531441, 708588,\n",
    "    1062882, 1594323, 2125764, 3188646, 4782969, 6377292, 9565938, 14348907,\n",
    "    19131876, 28697814, 43046721, 57395628, 86093442, 129140163, 172186884,\n",
    "    258280326, 387420489, 516560652, 774840978, 1162261467, 1549681956]\n",
    "    def integerBreak(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        return Solution.__ans[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerBreak(self, n):\n",
    "        if n == 2:\n",
    "            return 1\n",
    "        elif n==3:\n",
    "            return 2\n",
    "        result = 1\n",
    "        while n>4:\n",
    "            result *= 3\n",
    "            n -= 3\n",
    "        result *= n\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerBreak(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        \n",
    "        if n<2:\n",
    "            return False\n",
    "        if n==2:\n",
    "            return 1\n",
    "        if n==3:\n",
    "            return 2\n",
    "        memo = [0]*(n+1)\n",
    "        memo[0:4]=[0,0,1,2]\n",
    "        for i in range(4,n+1):\n",
    "            for j in range(1,i):\n",
    "                memo[i] = max(memo[i],j*memo[i-j],j*(i-j))\n",
    "        return memo[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerBreak(self, n: int) -> int:\n",
    "        dp = [0] * (n+1)\n",
    "        \n",
    "        for i in range(2, n+1):\n",
    "            for j in range(1, (i+1) // 2 + 1):\n",
    "                dp[i] = max(dp[i], max(j, dp[j]) * max(i-j, dp[i-j]))\n",
    "        \n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerBreak(self, n: int) -> int:\n",
    "        dp=[0,1]\n",
    "        for i in range(2,n+1):\n",
    "            num =[]\n",
    "            for k in range(1,i//2+1):\n",
    "                b=i-k\n",
    "                num.append(max(k,dp[k])*max(b,dp[b]))\n",
    "            dp.append(max(num))\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerBreak(self, n: int) -> int:\n",
    "        if n <= 3: return n - 1\n",
    "        a, b = n // 3, n % 3\n",
    "        if b == 0: return pow(3, a)\n",
    "        if b == 1: return pow(3, a - 1) * 4\n",
    "        return pow(3, a) * 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def integerBreak(self, n: int) -> int:\r\n",
    "        if n <= 2:\r\n",
    "            return 1\r\n",
    "        if n == 3:\r\n",
    "            return 2\r\n",
    "        x = n // 3\r\n",
    "        y = n % 3\r\n",
    "        if y == 0:\r\n",
    "            res = 3 ** x \r\n",
    "        elif y == 1:\r\n",
    "            res = 3 ** (x-1) * 4\r\n",
    "        else:\r\n",
    "            res = 3 ** x * 2\r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerBreak(self, n: int) -> int:\n",
    "        if n <= 3: return n - 1\n",
    "        a, b = n // 3, n % 3\n",
    "        if b == 0: return pow(3, a)\n",
    "        if b == 1: return pow(3, a - 1) * 4\n",
    "        return pow(3, a) * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerBreak(self, n: int) -> int:\n",
    "        dp = [0 for i in range(n+1)]\n",
    "        dp[2] = 1\n",
    "        for i in range(3, n+1):\n",
    "            dp[i] = max(2 * dp[i-2], 2 * (i-2), 3 * dp[i-3], 3 * (i-3))\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerBreak(self, n: int) -> int:\n",
    "        if n == 2:\n",
    "            return 1\n",
    "        if n == 3:\n",
    "            return 2\n",
    "        if n == 4:\n",
    "            return 4\n",
    "        sum = 1\n",
    "        while n > 4:\n",
    "            n = n - 3\n",
    "            sum = sum * 3\n",
    "        return sum * n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerBreak(self, n: int) -> int:\n",
    "\n",
    "        if n <= 3: return n - 1\n",
    "        a, b = n // 3, n % 3\n",
    "        if b == 0: return int(math.pow(3, a))\n",
    "        if b == 1: return int(math.pow(3, a - 1) * 4)\n",
    "        return int(math.pow(3, a) * 2)\n",
    "\n",
    "        # out = []\n",
    "        # def backtrack(candidate, tmp):\n",
    "        #     if sum(tmp) == n:\n",
    "        #         out.append(tmp)\n",
    "        #     elif sum(tmp) > n:\n",
    "        #         return\n",
    "\n",
    "        #     for idx in range(len(candidate)):\n",
    "        #         num = n // candidate[idx]\n",
    "        #         for idx_n in range(1, num + 1):\n",
    "        #             backtrack(candidate[idx + 1:], tmp + [candidate[idx]] * idx_n)\n",
    "\n",
    "        # if n >= 10:\n",
    "        #     backtrack(range(2, n), [])\n",
    "        # else:\n",
    "        #     backtrack(range(1, n), [])\n",
    "\n",
    "        # # def backtrack(rem, tmp):\n",
    "        # #     if sum(tmp) == n:\n",
    "        # #         out.append(tmp)\n",
    "        # #     elif sum(tmp) > n:\n",
    "        # #         return\n",
    "            \n",
    "        # #     for cdd in range(2, rem):\n",
    "        # #         num = n // cdd\n",
    "        # #         for idx_n in range(1, num + 1):\n",
    "        # #             backtrack(n - idx_n * cdd, tmp + [cdd] * idx_n)\n",
    "\n",
    "        # # backtrack(n, [])\n",
    "        # max_out = 0\n",
    "        # for cmb in out:\n",
    "        #     start = 1\n",
    "        #     for num in cmb:\n",
    "        #         start *= num\n",
    "            \n",
    "        #     if max_out < start:\n",
    "        #         max_out = start\n",
    "        \n",
    "        # return max_out"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#\n",
    "# @lc app=leetcode.cn id=343 lang=python3\n",
    "#\n",
    "# [343] 整数拆分\n",
    "#\n",
    "\n",
    "# @lc code=start\n",
    "class Solution:\n",
    "    def integerBreak(self, n: int) -> int:\n",
    "        dp = [0 for _ in range(n + 1)] \n",
    "        for i in range(2, n + 1):\n",
    "            curMax = 0\n",
    "            for j in range(1, i + 1):\n",
    "                curMax = max(curMax, max(j * (i - j), j * dp[i - j]))\n",
    "            dp[i] = curMax\n",
    "    \n",
    "        return dp[n]\n",
    "\n",
    "# @lc code=end\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import functools\n",
    "class Solution:\n",
    "    @functools.lru_cache(None)\n",
    "    def integerBreak(self, n: int) -> int:\n",
    "        if n==1:\n",
    "            return n\n",
    "        res=n-1\n",
    "        for i in range(2,n):\n",
    "            res=max(res,self.integerBreak(i)*(n-i),i*(n-i))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def integerBreak(self, n: int) -> int:\r\n",
    "        if n == 1:\r\n",
    "            return 0\r\n",
    "        if n == 2:\r\n",
    "            return 1\r\n",
    "        if n == 3:\r\n",
    "            return 2\r\n",
    "        d = {1:1, 2:2, 3:3}\r\n",
    "        def ok(component, self_returnable=True):\r\n",
    "            if component not in d:\r\n",
    "                ans = []\r\n",
    "                if self_returnable:\r\n",
    "                    ans.append(component)\r\n",
    "                for i in range(1, component//2+1):\r\n",
    "                    s = 1\r\n",
    "                    \r\n",
    "                    for new_component in [i, component-i]:\r\n",
    "                        if new_component not in d:\r\n",
    "                            d[new_component] = ok(new_component)\r\n",
    "                        print(\" \", new_component, d[new_component])\r\n",
    "                        s *= d[new_component]\r\n",
    "                    ans.append(s)\r\n",
    "                print(component, ans)\r\n",
    "                if self_returnable:\r\n",
    "                    return max(ans)\r\n",
    "                d[component] = max(ans)\r\n",
    "            return d[component]\r\n",
    "        tmp = ok(n, self_returnable=False)\r\n",
    "        print(d)        \r\n",
    "        return tmp\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerBreak(self, n: int) -> int:\n",
    "        if n<=3:\n",
    "            return n-1\n",
    "        ans = 1\n",
    "        while n>4:\n",
    "            ans*=3\n",
    "            n-=3\n",
    "        return ans*n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerBreak(self, n: int) -> int:\n",
    "        dp = [0] * (n + 1)\n",
    "        dp[2] = 1\n",
    "        for i in range(3, n+1):\n",
    "            for j in range(1, i+1):\n",
    "                dp[i] = max(dp[i], j * (i - j), j * dp[i - j])\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerBreak(self, n: int) -> int:\n",
    "        ## 动态规划 \n",
    "        ## dp[i]  表示i 被拆解能够达到的最大乘积\n",
    "\n",
    "        dp = [0]*(n+1)\n",
    "        dp[0] = 0\n",
    "        dp[1] = 1\n",
    "        dp[2] = 1\n",
    "\n",
    "        for i in range(3,n+1):\n",
    "\n",
    "            for j in range(1,i):## i 可以被进一步拆解  j=i 也不影响\n",
    "                dp[i] = max(dp[i],(i-j)*j,j*dp[i-j])\n",
    "\n",
    "        return dp[n]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerBreak(self, n: int) -> int:\n",
    "        # if n == 2:\n",
    "        #     return 1\n",
    "        # if n == 3:\n",
    "        #     return 2\n",
    "        # ans = dict()\n",
    "        # ans[1] = 1\n",
    "        # ans[2] = 1\n",
    "        # for i in range(2, n+1):\n",
    "        #     res = i\n",
    "        #     for j in range(1, i//2 + 1):\n",
    "        #         res = max(res, ans[j]*ans[i-j])\n",
    "        #     ans[i] = res\n",
    "        # return ans[n]\n",
    "        ans = [0, 0, 1, 2, 4, 6, 9, 12, 18, 27, 36, 54, 81, 108, 162, 243, 324, 486, 729, 972, 1458, 2187, 2916, 4374, 6561, 8748, 13122, 19683, 26244, 39366, 59049, 78732, 118098, 177147, 236196, 354294, 531441, 708588, 1062882, 1594323, 2125764, 3188646, 4782969, 6377292, 9565938, 14348907, 19131876, 28697814, 43046721, 57395628, 86093442, 129140163, 172186884, 258280326, 387420489, 516560652, 774840978, 1162261467, 1549681956]\n",
    "        return ans[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerBreak(self, n: int) -> int:\n",
    "        #d[i]: 数字i可以得到最大的乘积\n",
    "        d = [1] * (n+1)\n",
    "        if n < 3:\n",
    "            return 1\n",
    "        if n == 3:\n",
    "            return 2\n",
    "        d[2] = 2\n",
    "        d[3] = 3\n",
    "        for i in range(3, n + 1):\n",
    "            for j in range(1, i):\n",
    "                d[i] = max(d[i], d[j] * d[i - j])\n",
    "                d[i] = max(d[i], j * (i - j))\n",
    "            print(i, d[i])\n",
    "        return d[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerBreak(self, n: int) -> int:\n",
    "        @cache\n",
    "        def cal(p: int, k: int):\n",
    "            if k <= 2: return 1\n",
    "            if k == 3 and p == 1: return 2\n",
    "            ans = 0\n",
    "            for i in range(1, k + 1):\n",
    "                ans = max(ans, i * cal(p + 1, k - i))\n",
    "            return ans\n",
    "        return cal(1, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerBreak(self, n: int) -> int:\n",
    "        dp = [0] * (n+1)\n",
    "        dp[2] = 1\n",
    "        for i in range(3, n+1):\n",
    "            for j in range(1, i-1):\n",
    "                dp[i] = max(max(j*(i-j),j*dp[i-j]), dp[i])    # 取max dp[i]：每一层j保留一个最大的dp[i]\n",
    "        return dp[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerBreak(self, n: int) -> int:\n",
    "        dp = [1] * (n+1)\n",
    "        dp[2] = 1\n",
    "        for i in range(3, n+1):\n",
    "            for j in range(1, i-1):\n",
    "                dp[i] = max(dp[i], j * (i-j), j* dp[i-j])\n",
    "        \n",
    "        return dp[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def integerBreak(self, n: int) -> int:\n",
    "        dp = [0]*(n+1)\n",
    "        dp[2]=1\n",
    "        for i in range(3,n+1):\n",
    "            for j in range(1,i//2+1):\n",
    "                dp[i]=max(dp[i],(i-j)*j,dp[i-j]*j)\n",
    "        return dp[n]\n",
    "\n",
    "        \n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
